package pers.lls.hds.sort.recursion;

/**
 * 归迸排序
 *
 * @author lilichai
 */
public class MergeSort {

	long[] arr = {1,6,4,6,2,3,4};
	int size = 0;

	public void mergeSort() {
		long[] workSpace = new long[size];
		recMergeSort(workSpace, 0, size - 1);
	}

	private void recMergeSort(long[] workSpace, int lowerBound, int upperBound) {
		if (lowerBound == upperBound) {
			return;
		} else {
			int mid = (lowerBound + upperBound) / 2;

			recMergeSort(workSpace, lowerBound, mid);

			recMergeSort(workSpace, mid + 1, upperBound);

			merge(workSpace, lowerBound, mid + 1, upperBound);
		}
	}

	private void merge(long[] workSpace, int lowPtr, int highPtr, int upperBound) {
		int j = 0;
		int lowerBound = lowPtr;
		int mid = highPtr - 1;
		int n = upperBound - lowerBound + 1;

		while (lowPtr <= mid && highPtr <= upperBound) {
			if (arr[lowPtr] < arr[highPtr]) {
				workSpace[j++] = arr[lowPtr++];
			} else {
				workSpace[j++] = arr[highPtr++];
			}
		}

		while (lowPtr <= mid) {
			workSpace[j++] = arr[lowPtr++];
		}

		while (highPtr <= upperBound) {
			workSpace[j++] = arr[highPtr++];
		}

		for (j = 0; j < n; j++) {
			arr[lowerBound + j] = workSpace[j];
		}
	}

	public static void main(String[] args) {
		MergeSort mergeSort = new MergeSort();
		mergeSort.mergeSort();
	}

}

